package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

//判断链表是否为回文结构：普通的有两种解法，都使用栈结构，区别在于压入全部或压入右半部分。时间复杂度O(n)，额外空间复杂度O(n)
//进阶解法：获取中间节点后将右半部分反转，原本1->2->3->2->1反转后1->2->3<-2<-1，两端开始遍历判断相等即可（结束后记得将链表还原），时间复杂度O(n)，额外空间复杂度O(1)
public class IfLinkedListPalindrome {

    static class Node{
        private int value;
        private Node node;

        public Node(int value,Node node){
            this.value = value;
            this.node = node;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node){
            this.node = node;
        }
    }

    public boolean ifPalindrome(Node head){
        Stack<Integer> stack = new Stack<>();
        Node node = head;
        while(node != null){
            stack.push(node.getValue());
            node = node.getNode();
        }
        while(!stack.isEmpty()){
            if(stack.pop() != head.getValue()){
                return false;
            }
            head = head.getNode();
        }
        return true;
    }

    public boolean ifRightPalindrome(Node head){
        Stack<Integer> stack = new Stack<>();
        Node node = head;
        Node n2 = head.getNode();
        while(node.getNode() != null && node.getNode().getNode() != null){
            n2 = n2.getNode();
            node = node.getNode().getNode();
        }
        while(n2 != null){
            stack.push(n2.getValue());
            n2 = n2.getNode();
        }
        while(!stack.isEmpty()){
            if(stack.pop() != head.getValue()){
                return false;
            }
            head = head.getNode();
        }
        return true;
    }

    //进阶
    public boolean ifPalindromeQuick(Node head){
        Node node = head;
        Node temp = head;
        while(temp.getNode() != null && temp.getNode().getNode() != null){//寻找中间节点
            node = node.getNode();
            temp = temp.getNode().getNode();
        }
        temp = node.getNode();
        node.setNode(null);
        Node next;
        while(temp != null){//右半部分反转
            next = temp.getNode();
            temp.setNode(node);
            node = temp;
            temp = next;
        }
        temp = node;
        next = head;
        boolean result = true;
        while(next != null && node != null){//判断相等
            if(next.getValue() != node.getValue()){
                result = false;
                break;
            }
            next = next.getNode();
            node = node.getNode();
        }
        while(temp != null){//还原链表
            next = temp.getNode();
            temp.setNode(node);
            node = temp;
            temp = next;
        }
        return result;
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        String[] numbers = scanner.readLine().split(" ");
        Node node = null;
        for(int i = len - 1;i >= 0;i--){
            node = new Node(Integer.parseInt(numbers[i]),node);
        }
//        boolean b = new IfLinkedListPalindrome().ifPalindrome(node);
//        boolean b = new IfLinkedListPalindrome().ifRightPalindrome(node);
        boolean b = new IfLinkedListPalindrome().ifPalindromeQuick(node);
        System.out.print(b);
    }
}
